package function;

import java.util.Arrays;
	/*使用数组实现的队列，在ParkAndSidewalk类中使用
	 * 使用队列模拟便道
	 */
public class Queue<T> {
	private int DEFAULT_SIZE = 12;
	private int capacity;// 保存数组的长度，即队列长度
	private T[] elementData;// 定义一个数组用于保存顺序队列的元素
	private int front = 0;// 队首
	private int rear = 0;// 队尾

	public Queue() {
		capacity = DEFAULT_SIZE;
		elementData = (T[]) new Object[capacity];
	}

	public Queue(int initSize) {
		elementData = (T[]) new Object[initSize];
	}

	public Queue(T[] list) {
		this();
		for (int i = 0; i < list.length; i++) {
			this.enQueue(list[i]);
		}
	}

	/**
	 * @Title: size
	 * @Description: 获取顺序队列的大小
	 * @return
	 */
	public int size() {
		return rear - front;
	}

	/**
	 * @Title: enQueue
	 * @Description: 入队列
	 * @param element
	 */
	public void enQueue(T element) {
		//先调用ensureCapacity方法保证数组容量够用
		ensureCapacity(rear + 1);
		elementData[rear++] = element;
	}
	//保证数组容量够用
	private void ensureCapacity(int minCapacity) {
		int oldCapacity = elementData.length;
		// 如果数组的原有长度小于目前所需的长度
		if (minCapacity > oldCapacity) {
			int newCapacity = (oldCapacity * 3) / 2 + 1;
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			elementData = Arrays.copyOf(elementData, newCapacity);
		}

	}

	/**
	 * @Title: deQueue
	 * @Description: 出队列
	 * @return
	 */
	public T deQueue() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("空队列异常");
		}
		// 保留队列的front端的元素的值
		T oldValue = elementData[front];
		// 释放队列的front端的元素
		elementData[front++] = null;
		return oldValue;
	}

	/**
	 * @Title: getTop
	 * @Description: 返回队首元素，但不删除队首元素
	 * @return
	 */
	public T getTop() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("空队列异常");
		}
		return elementData[front];
	}

	/**
	 * @Title: isEmpty
	 * @Description: 判断顺序队列是否为空队列
	 * @return
	 */
	public boolean isEmpty() {
		return rear == front;
	}

	/**
	 * @Title: clear
	 * @Description: 清空顺序队列
	 */
	public void clear() {
		// 将数组所有元素赋为null
		Arrays.fill(elementData, null);
		front = 0;
		rear = 0;
	}
	public String toString() {
		if (isEmpty()) {
			return "[]";
		} else {
			StringBuilder sb = new StringBuilder("[");
			for (int i = front; i < rear; i++) {
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2, len).append("]").toString();
		}
	}
}
